package zw_1_100.zw_94_二叉树的中序遍历;


import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {

    /**
     * 递归
     * 前序遍历：打印 - 左 - 右
     * 中序遍历：左 - 打印 - 右
     * 后序遍历：左 - 右 - 打印
     * 题目要求的是中序遍历，那就按照 左-打印-右这种顺序遍历树就可以了，递归函数实现
     * 终止条件：当前节点为空时
     * 函数内：递归的调用左节点，打印当前节点，再递归调用右节点
     * 时间复杂度：O(n)；空间复杂度：O(h)，h 是树的高度
     * @param root
     * @return
     */
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> res = new ArrayList<Integer>();
//        dfs(res,root);
//        return res;
//    }
//    void dfs(List<Integer> res, TreeNode root) {
//        if(root==null) {
//            return;
//        }
//        //按照 左-打印-右的方式遍历
//        dfs(res,root.left);
//        res.add(root.val);
//        dfs(res,root.right);
//    }

    /**
     * 迭代实现
     * 递归的调用过程是不断往左边走，当左边走不下去了，就打印节点，并转向右边，然后右边继续这个过程。
     * 我们在迭代实现时，就可以用栈来模拟上面的调用过程。
     * @param root
     * @return
     */
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> res = new ArrayList<Integer>();
//        Stack<TreeNode> stack = new Stack<TreeNode>();
//        while(stack.size()>0 || root!=null) {
//            //不断往左子树方向走，每走一次就将当前节点保存到栈中
//            //这是模拟递归的调用
//            if(root!=null) {
//                stack.add(root);
//                root = root.left;
//                //当前节点为空，说明左边走到头了，从栈中弹出节点并保存
//                //然后转向右边节点，继续上面整个过程
//            } else {
//                TreeNode tmp = stack.pop();
//                res.add(tmp.val);
//                root = tmp.right;
//            }
//        }
//        return res;
//    }


    /**
     * Morris 中序遍历
     * https://leetcode.cn/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        TreeNode predecessor = null;

        while (root != null) {
            if (root.left != null) {
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }

                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor.right == null) {
                    predecessor.right = root;
                    root = root.left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {
                    res.add(root.val);
                    predecessor.right = null;
                    root = root.right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }





    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
